package com.zjsru.plan2024.oneday;

/**
 * 1186. 删除一次得到子数组最大和
 * @Author: cookLee
 * @Date: 2024-07-21
 */
public class MaximumSum {

    /**
     * 主
     * \
     * 输入：arr = [1,-2,0,3]
     * 输出：4
     * 解释：我们可以选出 [1, -2, 0, 3]，然后删掉 -2，这样得到 [1, 0, 3]，和最大。
     * \
     * 输入：arr = [1,-2,-2,3]
     * 输出：3
     * 解释：我们直接选出 [3]，这就是最大和。
     * \
     * 输入：arr = [-1,-1,-1,-1]
     * 输出：-1
     * 解释：最后得到的子数组不能为空，所以我们不能选择 [-1] 并从中删去 -1 来得到 0。
     *      我们应该直接选择 [-1]，或者选择 [-1, -1] 再从中删去一个 -1。
     * \
     * @param args args
     */
    public static void main(String[] args) {
        MaximumSum maximumSum = new MaximumSum();
        int[] arr = new int[]{1,-2,0,3};
        System.out.println(maximumSum.maximumSum(arr));
    }

    /**
     * 最大总和：动态规划
     *
     * @param arr arr
     * @return int
     */
    public int maximumSum(int[] arr) {
        int ans = arr[0];
        int dp0 = arr[0];
        int dp1 = 0;
        for (int i = 1; i < arr.length; i++) {
            //表示在不删除的情况下，子数组的最大和
            dp1 = Math.max(dp0, dp1 + arr[i]);
            //表示在删除一次的情况下，子数组的最大和
            dp0 = Math.max(dp0, 0) + arr[i];
            ans = Math.max(ans, Math.max(dp0, dp1));
        }
        return ans;
    }

}
